1. Field of the Invention
The present invention relates to controlling packet congestion. More particularly, the present invention relates to controlling packet congestion in which fair queuing of packets is effected using an Active Flow Random Early Drop (AFRED) method to guarantee Quality of Service (QoS).
2. Description of the Related Art
A typical method of resolving a congestion problem on the Internet is to control a transmission rate through a window size of a transmitting host in response to congestion which has already occurred and which depends on only both ends TCP hosts. However, since this method is unable to resolve the congestion which has already occurred, it is not sufficient to cope with an explosive traffic increase that the Internet has undergone.
When the congestion has already occurred, a queue length in a router buffer located at a congestion spot has already reached a maximum value, and so all packets following the congestion are dropped. Thus, all transmission hosts which have transmitted the packets almost simultaneously enter a slow start mode which reduces a window size, whereby a rate using a link falls.
In order to solve such problems, there is a need for a technique of actively coping with congestion before it occurs by managing buffers of a router (or gateway) which is an intermediate node, together with a current source based congestion control technique which controls a transmission rate of the end transmission hosts on the network. This can not only prevent the link use rate from falling but also always keeps a short queue length in the router.
An important objective of a congestion control technique is to maintain a small queue length at an intermediate node since a queuing delay of a network intermediate node greatly affects a total packet processing rate as it goes to a high speed network.
Various techniques for network congestion control have been proposed including a round robin scheduling technique to allocate a fair bandwidth to respective data streams.
However, a data stream can be allocated too much bandwidth or no bandwidth since a limited bandwidth is used.
In the typical per-flow queuing method, separated queues for respective flows are prepared, and the separated queues are separately managed according to a round robin scheduling method. Thus, fair queuing is possible since the queues are managed by the round robin scheduling method. A system which uses the per-flow queuing has advantages of not only reducing a packet loss problem resulting from congestion but also reducing buffer requirements. On the other hand, there is also a disadvantage in that because the separated queues must be managed based on each flow in the equipment, it is difficult to implement a fair allocation mechanism.
In a FIFO method, all flows flow into a single queue, and the flows are not separately managed. When congestion occurs, a packet is dropped so that a sender can be notified of the congestion, and a gateway (or router) can anticipate a network state by monitoring a queue length. If the queue length is long and an incoming packet is dropped, the sender reacts to such a packet loss. Such a simple packet management method is called the Drop Tail method. That is, this method drops an incoming packet when a buffer is completely filled. This means that a packet transmission rate depends on the performance of a link.
As a method of solving the Drop Tail problem, there is a concept of anticipating and detecting a congestion situation on the network in advance at an intermediate node and then informing the sender of the congestion. The sender is warned of a packet loss in advance so that the sender can adjust a transmission rate when a packet is forcibly dropped due to the network congestion.
This concept is known as “congestion avoidance” method. A purpose of the congestion avoidance method is to prevent an excessive queue size to thereby reduce the packet loss and to make a small size queue adequately use a non-used bandwidth of the link, thereby enabling the communication network to be optimally used. One of such strategies is a Random Early Detection (RED) method proposed by the Internet Engineer Task Force (IETF).
The RED method determines a congestion level of a network according to an average queue length and then calculates a packet drop probability. The RED method has a higher link use rate than the Drop Tail method.
The RED method enables an adequate use of a buffer by observing an average size of a queue. When the average queue size exceeds a previously set threshold size, the packets are randomly selected to be dropped or marked, thereby preventing the network from reaching a congestion state.
However, when the packets are dropped by the RED method, the packets may be processed without considering fairness for respective flows or any specialty for specific service (e.g., video service). This is because the RED method is based on the FIFO method.
Also, the parameters used in the RED method do vary according to a network condition and are fixed values which are set at an initial stage, and the packets are processed (dropped or accepted) based on these fixed values. Thus, it is impossible to take adequate measures for packet flows which need a predetermined bandwidth such as a video service.
The following patents each discloses features in common with the present invention but do not teach or suggest the inventive features specifically recited in the present claims: U.S. patent application No. 2002/0009051 to Cloonan, entitled CONGESTION CONTROL IN A NETWORK DEVICE HAVING A BUFFER CIRCUIT, published on Jan. 24, 2002; U.S. Pat. No. 5,838,677 to Kozaki et al., entitled SWITCHING SYSTEM HAVING MEANS FOR CONGESTION CONTROL BY MONITORING PACKETS IN A SHARED BUFFER AND BY SUPPRESSING THE READING OF PACKETS FROM INPUT BUFFERS, issued on Nov. 17, 1998; U.S. Pat. No. 5,090,011 to Fukuta et al., entitled PACKET CONGESTION CONTROL METHOD AND PACKET SWITCHING EQUIPMENT, issued on Feb. 18, 1992; U.S. Pat. No. 6,724,721 to Cheriton, entitled APPROXIMATED PER-FLOW RATE LIMITING, issued on Apr. 20, 2004; U.S. Pat. No. 6,671,258 to Bonneau, entitled DYNAMIC BUFFERING SYSTEM HAVING INTEGRATED RANDOM EARLY DETECTION, issued on Dec. 30, 2003; U.S. Pat. No. 6,556,578 to Silberschatz et al. entitled EARLY FAIR DROP BUFFER MANAGEMENT METHOD, issued on Apr. 29, 2003; U.S. Pat. No. 6,252,848 to Skirmont, entitled SYSTEM PERFORMANCE IN A DATA NETWORK THROUGH QUEUE MANAGEMENT BASED ON INGRESS RATE MONITORING, issued on Jun. 26, 2001; U.S. Pat. No. 6,515,963 to Bechtolsheim et al. entitled PER-FLOW DYNAMIC BUFFER MANAGEMENT, issued on Feb. 4, 2003; U.S. Pat. No. 6,205,149 to Lemaire et al. entitled QUALITY OF SERVICE CONTROL MECHANISM AND APPARATUS, issued on Mar. 20, 2001; U.S. patent application No. 2004/0071086 to Haumont et al. entitled TRAFFIC CONGESTION, published on Apr. 15, 2004; U.S. patent application No. 2003/0231593 to Bauman et al. entitled FLEXIBLE MULTILEVEL OUTPUT TRAFFIC CONTROL, published on Dec. 18, 2003; U.S. patent application No. 2003/0223362 to Mathews et al. entitled RANDOM EARLY DROP WITH PER HOP BEHAVIOR BIASING, published on Dec. 4, 2003; U.S. patent application No. 2003/0088690 to Zuckerman et al. entitled ACTIVE QUEUE MANAGEMENT PROCESS, published on May 8, 2003; and U.S. patent application No. 2003/0007454 to Shorey, entitled TRAFFIC MANAGEMENT IN PACKET-BASED NETWORKS, published on Jan. 9, 2003.